package com.arron.algorithm.leetcodetop100.链表;

import com.arron.algorithm.leetcodetop100.ListNode;
import com.arron.myhash.HashMapTest;

/**
 * Leetcode 876. 链表的中间结点
 *
 *
 */
public class 链表的中间结点 {


    /**
     * 使用双指针 ，快慢指针寻找中间位置
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {

        if (head == null || head.next ==null) return head;

        ListNode slowNode = head;
        ListNode fastNode = head;

        while (fastNode !=null && fastNode.next != null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        return slowNode;
    }


    /**
     * Leetcode 19 删除链表中倒数第k个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        //找到 倒数 第k个节点
        ListNode node = getKthFromEnd1(head, n);
        //删除
        removeNode(head,node);
        return node;
    }

    public void removeNode(ListNode head ,ListNode node){
        ListNode p1 = head;
        while (p1!=null){
            if (p1.next == node){
                p1.next = p1.next.next;
                node.next = null;
                break;
            }
            p1 = p1.next;
        }
    }


    //剑指 Offer 22. 链表中倒数第k个节点
    public ListNode getKthFromEnd0(ListNode head, int k) {

        if (head ==null || head.next ==null) return head;

        ListNode p = head;

        int len = 0,i=1,num =0; //链表长度

        while (p!=null){
            p = p.next;
            len++;
        }
        //将倒数第k个转换为正数第k个
        num = len -k+1;
        p= head;

        while (p!=null){
            if (i==num){
                break;
            }
            p=p.next;
            i++;
        }
        return p;
    }

    //使用双指针，找到倒数第k个节点
    public ListNode getKthFromEnd1(ListNode head, int k) {
        if (head ==null || head.next ==null) return head;

        ListNode p1 = head;
        ListNode p2 = head;
        int i=0;
        //先将指针p2移动k步，此时p2和p1相差k个节点
        while (i<k){
            p2 = p2.next;
            i++;
        }
        //两个指针同时移动
        while (p2!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
       return p1;
    }



}
